package leetcode_core.leetcode_4;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2022年10月16日 9:50
 */
public class IsBipartite {
    private boolean ok = true;//假定还是ok的
    private boolean[] color;
    private boolean[] visited;
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        color = new boolean[n];
        visited = new boolean[n];
        //然后遍历整张表
        for(int i = 0;i<n;i++){
            if(!visited[i]){
                dfs(graph,i);
            }
        }
        return ok;
    }
    //遍历对象
    //v是当前节点
    private void dfs(int[][] graph,int v){
        if(!ok){
            return ;//那么就不必再寻找了
        }
        //否则的话还是需要继续遍历的
        int[] lists = graph[v];//获得当前节点v的所有邻接点
        for (int point : lists) {
            if(!visited[point]){
                //如果没有访问过,那么就为它染色
                color[point] = !color[v];//为他染色
                dfs(graph,point);
            }else{
                //否则的话就是访问过的,我们检查它的染色情况
                if(color[point] == color[v]){
                    ok = false;
                    return ;
                }
            }
        }
    }
}
